import java.util.*;

public class Solution {
    //JZ22 链表中倒数最后k个结点
    public ListNode FindKthToTail (ListNode pHead, int k) {
        int len=size(pHead);
        if(pHead==null||k>len){
            return null;
        }
        ListNode slow=pHead;
        ListNode fast=pHead;
        while(k>0){
            fast=fast.next;
            k--;
        }
        while(fast!=null){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }
    //求长度
    public int size(ListNode pHead){
        ListNode cur=pHead;
        int count=0;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    //使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，
    // 并保证奇数和奇数，偶数和偶数之间的相对位置不变。
    public int[] reOrderArray (int[] array) {
        Queue<Integer> q1=new LinkedList<>();//入奇数
        Queue<Integer> q2=new LinkedList<>();//入偶数
        for (int i = 0; i <array.length ; i++) {
            if(array[i]%2==0){
                q2.offer(array[i]);
            }else{
                q1.offer(array[i]);
            }
        }
        int count=0;
        while(!q1.isEmpty()){
            array[count++]= q1.poll();
        }
        while(!q2.isEmpty()){
            array[count++]= q2.poll();
        }
        return array;
    }
    //用两个栈实现队列
    Stack<Integer> stack1 = new Stack<Integer>();//假定s1入队
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);
    }

    public int pop() {
        if (stack1.empty() && stack2.empty()) {
            return -1;
        }
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}
class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> s1 = new Stack<>();
        int count = 0;
        ListNode cur = listNode;
        while (cur != null) {
            count++;
            s1.push(cur.val);
            cur = cur.next;
        }
        ArrayList<Integer> arr = new ArrayList<Integer>(count);
        int i = 0;
        while (!s1.empty()) {
            int k = s1.pop();
            arr.add(k);
        }
        return arr;
    }

    //JZ5 替换空格
    public String replaceSpace1(String s) {
        //查找有多少个空格
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == ' ') {
                count++;
            }
        }
        //开辟一个字符数组
        int len = count * 2 + s.length();
        char[] arr = new char[len];
        int count1 = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != ' ') {
                arr[count1] = s.charAt(i);
                count1++;
            } else {
                arr[count1] = '%';
                arr[count1 + 1] = '2';
                arr[count1 + 2] = '0';
                count1 = count1 + 3;
            }
        }
        String x = new String(arr);
        return x;
    }

    //JZ4 二维数组中的查找
    public boolean Find(int target, int[][] array) {
        if (array.length == 0 || array[0].length == 0) {
            return false;
        }
        for (int i = 0; i < array.length; i++) {
            if (target >= array[i][0]) {
                for (int j = 0; j < array[i].length; j++) {
                    if (target == array[i][j]) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}
